Ví dụ Thuật_toán_Ford–Fulkerson

Ví dụ sau đây cho thấy những bước ban đầu của thuật toán Ford-Fulkerson trong một mạng vận tải gồm 4 nút, nguồn A và thoát D. Các đường đi tăng được tìm bằng phương pháp tìm kiếm theo chiều sâu, trong đó các đỉnh lân cận được duyệt theo thứ tự bảng chữ cái. Ví dụ này cho thấy biểu hiện của trường hợp xấu nhất của thuật toán. Mỗi bước chỉ gửi thêm được một luồng giá trị 1 qua mạng. Nếu sử dụng phép tìm theo chiều rộng thay vì theo chiều sâu, ta sẽ chỉ cần hai bước.

Đường điKhả năng thông quaMạng đạt được
Mạng vận tải ban đầu
A , B , C , D {\displaystyle A,B,C,D}

min ( c f ( A , B ) , c f ( B , C ) , c f ( C , D ) ) = {\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=}
min ( c ( A , B ) − f ( A , B ) , c ( B , C ) − f ( B , C ) , c ( C , D ) − f ( C , D ) ) = {\displaystyle \min(c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D))=}
min ( 1000 − 0 , 1 − 0 , 1000 − 0 ) = 1 {\displaystyle \min(1000-0,1-0,1000-0)=1}

A , C , B , D {\displaystyle A,C,B,D}

min ( c f ( A , C ) , c f ( C , B ) , c f ( B , D ) ) = {\displaystyle \min(c_{f}(A,C),c_{f}(C,B),c_{f}(B,D))=}
min ( c ( A , C ) − f ( A , C ) , c ( C , B ) − f ( C , B ) , c ( B , D ) − f ( B , D ) ) = {\displaystyle \min(c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B,D))=}
min ( 1000 − 0 , 0 − ( − 1 ) , 1000 − 0 ) = 1 {\displaystyle \min(1000-0,0-(-1),1000-0)=1}

… {\displaystyle \dots }
Mạng vận tải cuối cùng

Chú ý khi luồng bị "đẩy ngược" từ C đến B khi tìm được đường đi A,C,B,D.